LEE CHANWOO

📝 Blog 2024 version 1.5.1
🔖 JUN 15, 2024

5 분 소요

image


Virtual Memory Organization


Virtual memory concept

  • Concept
    • A technique that allows the execution of processes that are not completely in memory
      • Partition each user’s program into multiple blocks
      • Load into memory the blocks that is necessary at each time during execution
        • Noncontiguous allocation
      • Logical memory size is not constrained by the amount of physical memory that is available
    • Separation of logical memory as perceived by users from physical memory


  • Benefits
    • Easier programming
      • Programmer no longer needs to worry about the amount of physical memory available
    • Higher multiprogramming degree
      • Increase in CPU utilization and throughput (not in response time and turnaround time)
    • Less I/O for loading and swapping processes into memory
      • Faster execution of processes


  • Drawbacks
    • Address mapping overhead
    • Page fault handling overhead
    • Should be carefully used in real-time (embedded) systems


  • Methods
    • Paging (Demand paging)
      • Partition each user’s program into same size blocks
    • Segmentation
      • Partition each user’s program into logical blocks of different sizes
    • Hybrid paging/segmentation


Address Mapping

Case: Contiguous allocation

  • Executable memory images can be built by relocation (Load-time binding)
    • Relative address
      • Start address of the program: 0
  • Relocation
  • Transforming relative addresses (address constants) in the program to the corresponding physical addresses according to the allocation address of the program


image


Case: Noncontiguous allocation

  • Virtual address = relative address
  • Real address = absolute(physical) address
  • Address mapping
    • Difficult to implement load-time binding
    • Virtual address to real address transformation at run-time


Notes

  • Virtual address space
    • Refers to the logical (virtual) view of how a process is stored in memory


image


  • Sparse address space
    • Virtual address space that includes holes
    • Beneficial because the holes can be filled as the stack or heap segments grow or can be used when we wish to dynamically link libraries (shared objects) during program execution


  • Shared library in virtual memory

image


image


Block mapping


Block mapping

  • Block mapping
    • Partition user programs into blocks
    • Maintain address mapping information for each block of the program
  • Block map table
    • Keep virtual address, corresponding real address, and other information, for each block of the program


Virtual address v = (b, d)

  • b = block number
  • d = displacement(offset) in a block


image


Block map table

  • Maintains address mapping information
    • One BMT for each process in the system
    • In the kernel space

image


Block mapping procedure

image


image


Demand Paging


Paging System


Paging (Demand paging) system

  • Partition the program into the same size blocks (pages)
  • Loading of executable program
    • Initially, load pages only as they are needed
    • During execution, load the pages when they are demanded (referenced)
      • Pages that are never accessed are never loaded into physical memory
      • 필요 없는 페이지는 다시 내보내기도 한다.


image


Terminologies

  • Page
  • Page frame
  • Pager
    • Swaps a page into memory when the page is referenced
    • Concerned with the individual pages of a process


  • Swapper
    • Manipulates entire process
    • Swaps entire process into memory


Characteristics of paging system

  • No logical partition of the program
  • Simple and efficient
  • Used in most operating systems
  • Complex for sharing and protection

Address mapping

  • Virtual address v = (p, d) in paging systems
    • p = page number
    • d = displacement(offset)
  • Address mapping
    • Uses PMT (Page Map Table)
  • Address mapping mechanisms
    • Direct mapping
    • Associative mapping
      • TLB(Translation Look-aside Buffer)
    • Hybrid direct/associative mapping


  • Page map table

image


Address Mapping in Paging S.


Direct mapping

  • Similar to block mapping mechanisms
  • Assumptions
    • PMT resides in kernel space of main memory
    • PMT entry size = entrySize
    • Page size = pageSize


image


image


Problems in direct mapping

  • Doubles the number of memory accesses during execution of the program
  • Performance degradation
  • PMT size


Solutions

  • Associative mapping (TLB)
  • Implement the PMT using the dedicated registers or cache memories


Associative mapping

  • TLB(Translation Look-aside Buffer)
    • Associative high-speed memory
  • Parallel search on PMT
  • Low overhead, high speed
  • Expensive hardware


image


Hybrid direct/associative mapping

  • Uses direct mapping and associative mapping, simultaneously
    • Low hardware cost
    • Take advantage of associative mapping
  • Small TLB
    • Full PMT: maintained in kernel space of the memory
    • Subset of PMT entries: maintained in TLB
      • Entries of the recently used pages


image

Locality - 한 번 접근된 페이지는 또 다시 접근될 가능성이 많다.


image


image


Effective memory access time (EAT)

  • TLB search: 20ns
  • Memory access time: 100ns
  • TLB hit ratio: 80%
    • EAT = 0.8(20 + 100) + 0.2(20 + 100 + 100) = 140ns
    • 40% slowdown in memory access time
  • TLB hit ratio: 98%
    • EAT = 0.98(20 + 100) + 0.02(20 + 100 + 100) = 122ns
    • 22% slowdown in memory access time


Other page table structures

  • Page-table registers
  • Hierarchical paging
  • Hashed page table
  • Inverted page table


Issues in Demand Paging


Page Sharing


Sharable pages

  • Procedure pages
    • Pure code (reentrant code)
  • Data page
    • Read-only data
      • Sharable without any restriction
    • Read-write data
      • Sharable under the concurrency control mechanism


image


image


image


Page Fault Handling

  • A crucial requirement for demand paging
    • Restart any instruction after a page fault
    • Example (steps to execute and instruction)

image


Performance of Paging System


Effective access time

  • Memory access time
    • 10 ~ 200 nanoseconds (Assume 100ns)
  • Average paging service time: about 8 milliseconds
  • Page fault rate: p (0  p  1)
  • EAT(Effective Access Time)
    • EAT = (1-p)ma + ppagingTime
      • = (1-p)100 + p8,000,000
      • = 100 + 7,999,900p
    • When p = 1/1000, EAT = 8.1 microseconds ( 80ma)
  • If we want less than 10% degradation,
    • EAT = 100 + 7,999,900p < 110
    • p < 0.00000125 ( 1/800,000)


….


Segmentation & Hybrid Paging/Segmentation


Segmentation system

  • Partition user program into logical blocks with possibly different sizes
  • Segment
    • Logically partitioned block
  • Characteristics
    • Pre-partition of main memory is not good in this case
    • Main memory management can be done similarly to VPM
    • Easy segment sharing and protection
    • Larger overhead in address mapping and memory management


image


Address mapping

  • Virtual address in segmentation system: v = (s, d)
    • s = segment number
    • d = displacement in a segment
  • SMT(Segment Map Table)
  • Address mapping mechanisms
    • Similar to them of paging system


image


Address Mapping in Seg. System


Direct mapping

  • Assumptions
    • SMT in kernel space of memory
    • Entry size of SMT = entrySize


image


image


Memory Mgm’t in Seg. Systems


  • Memory management
    • Similar to VPM
    • Initially, 1 partition in memory
    • Placement strategies
      • First fit
      • Best fit
      • Worst fit
      • Next fit


image


Hybrid Paging/Segmentation


Paging System

  • Advantages
    • Simple and low overhead
  • Disadvantages
    • No logical concept in partitioning programs
    • Complicated page sharing mechanism


Segmentation System

  • Advantages
    • Logical concept in partitioning programs
    • Simple and easy sharing mechanism
  • Disadvantages
    • Management overhead


Hybrid paging/segmentation

  • Take advantages of the paging/segmentation systems
  • Program partition
    • User program is partitioned into logical segments
    • Each segment is partitioned again into pages
  • Loading
    • Loading unit: page


image


Address mapping

  • Virtual address in hybrid systems: v = (s, p, d)
    • s = segment number
    • p = page number in a segment
    • d = offset in a page
  • Uses both SMT and PMT
    • One SMT for each process
    • One PMT for each segment in the program
  • Address mapping
    • Direct, associative, etc.
  • Memory
    • Pre-partitioned into page frames


image


image


image


image


Summary

  • Virtual memory concept
  • Address mapping
  • Demand paging
    • Address mapping
      • Direct mapping, associative mapping, hybrid mapping, page table registers, hierarchical paging, hashed page table, inverted page table
    • Issues in demand paging
      • Page sharing, page fault handling, performance, copy-on-write, memory-mapped files, kernel memory allocation
  • Segmentation
  • Hybrid paging/segmentation

댓글남기기

참고